// -----------------------------
// projects/c++/primes/main.c++
// -----------------------------

/*
 To run the tests:
 % g++ -ansi -pedantic -lcppunit -ldl -Wall -DTEST main.c++ -o main.app
 % valgrind main.app
 
 To run the program:
 % g++ -ansi -pedantic -Wall main.c++ -o main.app
 % valgrind main.app < Primes.in > Primes.out
 
 To configure Doxygen:
 doxygen -g
 That creates the file Doxyfile.
 Make the following edits:
 EXTRACT_ALL            = YES
 EXTRACT_PRIVATE        = YES
 EXTRACT_STATIC         = YES
 GENERATE_LATEX         = NO
 
 To document the program:
 doxygen Doxyfile
 */

// --------
// includes
// --------

#include <cassert>  // assert
#include <iostream> // cin, cout, endl, ios_base, istream, ostream

#ifdef TEST
#include "cppunit/TestSuite.h"      // TestSuite
#include "cppunit/TextTestRunner.h" // TestRunner
#endif // TEST

// -------
// defines
// -------

#ifdef ONLINE_JUDGE
#define NDEBUG
#endif

// -------
// globals
// -------

const int PRIME_MAX = 5200000;

// array of primality. O-index, so if isPrime[n] = true, then n+1 is prime
//                                 if isPrime[n] = false, then n+1 is composite
bool isPrime[PRIME_MAX]; //= { true };
int sum;
int addend[4];

// ----
// read
// ----

/**
 * @brief Reads an int into sum
 * @param in an input stream
 * @return true if that succeeds, false otherwise
 */
bool read (std::istream& in) {
    if (!(in >> sum))
        return false;
    return true;
}

// ---------
// nextPrime
// ---------

/**
 * @brief Returns as an integer the next prime number after n.
 * @param n the prime number.
 * @pre n is > 0
 * @post none.
 * @return integer of the next prime number after n.
 */
inline int nextPrime(int n) {
    assert(n > 0);
    // nextPrime is the number being tested to see if it is the next prime

    int nextPrime = n + 1;
    for (; !isPrime[nextPrime] && nextPrime < PRIME_MAX; nextPrime++);
    
    if (nextPrime >= PRIME_MAX) return -1;
    return nextPrime;
}


// ----
// eval
// ----

/**
 * @brief Finds prime numbers that add up to sum and stores the primes in addend.
 * @pre sum is < 10,000,001
 * @post All numbers in addend are prime numbers.
 */
void eval () {
    assert(sum < 10000001);

    // if it is impossible, return -1
    if (sum < 8) {
        addend[0] = addend[1] = addend[2] = addend[3] = -1;
        return;
    }

    // partialSum is the difference of sum - addend[0] - addend[1]
    // i is a loop index
    int partialSum, i = 0;
    
    //if sum is even
    if(sum % 2 == 0) {
        addend[0] = addend[1] = 2;
    } else {
    // if sum is odd
        addend[0] = 2;
        addend[1] = 3;
    }

    partialSum = sum - addend[0] - addend[1];
    addend[2] = addend[3] = 1;
    
    // while addend[3] is not prime
    while (!isPrime[addend[3]]) {
        // while addend[3] is not prime
        addend[2] = nextPrime(addend[2]);
        // if addend[2] exhausted all primes in the PRIME_MAX range, break
        if(addend[2] == -1) break;
        
        addend[3] = partialSum - addend[2];
        assert((addend[0] + addend[1] + addend[2] + addend[3]) == sum);
        
        //if addend[3] is bigger than PRIME_MAX, make addend[2] bigger
        while(addend[3] > PRIME_MAX) {
            addend[2] = nextPrime((partialSum/2) + i++);
            addend[3] = partialSum - addend[2];
        }
    }

    assert(isPrime[addend[0]] && isPrime[addend[1]] && isPrime[addend[2]] && isPrime[addend[3]]);
}


// ----------
// findPrimes
// ----------

/**
 * @brief Finds prime numbers and marks them in an array.
 * If isPrime[n] = true, then n is prime.  If isPrime[n] = false, then n is
 *  composite.
 * @pre none.
 * @post none.
 */
void findPrimes() {
    // i and j are loop indices
    int i, j;
    
    // 0 and 1 are not prime
    isPrime[0] = isPrime[1] = false;
    // init isPrime array to all true
    for(i = 2; i < PRIME_MAX; i++)
        isPrime[i] = true;
  
    // loop through all values in isPrime array up to PRIME_MAX, marking
    // each multiple of a prime as false (not prime) in the array
    for (i = 2; i < PRIME_MAX; i++) {

        // if this is composite, skip it
        if (!isPrime[i]) continue;

        // if prime, mark all multiples as composite
        for(j = i*2; j < PRIME_MAX; j+=i) {
            isPrime[j] = false;
        }
    }
}

// -----
// print
// -----

/**
 * @brief Prints the values of addend.
 * @param out an output stream.
 * @pre none.
 * @post none.
 */
void print (std::ostream& out) {
    if (addend[0] > 0) {
        out << addend[0] << " " << addend[1] << " "
            << addend[2] << " " << addend[3] << std::endl;
    } else {
        out << "Impossible." << std::endl;
    }
}

// -----
// tests
// -----

#ifdef TEST
#include "TestPrimes.h"
#endif // TEST

// ----
// main
// ----

/**
 * @brief Main function that either runs the tests or runs the program.  It
 * reads the input, evaluates it and prints the result.
 * @pre none.
 * @post none.
 * @return integer representing the exit status of the program.
 */
int main () {
    using namespace std;
    ios_base::sync_with_stdio(false); // turn off synchronization with C I/O
    
#ifdef TEST
    // ----------
    // unit tests
    // ----------
    
    findPrimes();
    CppUnit::TextTestRunner tr;
    tr.addTest(TestPrimes::suite());
    tr.run();
#else
    // -------
    // program
    // -------
    
    findPrimes();

    while (read(cin)) {
        eval();
        print(cout);
    }

#endif // TEST
    
    return 0;
}
